Techniques for drawing digraphs are known. For example, FIG. 1A illustrates a graph drawn with one known algorithm by Sugiyama. [See K. Sugiyama, S. Tagawa and M. Toda, “Methods for Visual Understanding of Hierarchical Systems”, IEEE Trans. Systems, Man, and Cybernetics 11 (1981), 109-125]. In the Sugiyama algorithm, the y-coordinates are computed by dividing the y-axis into a finite number of layers and associating each node with exactly one layer. Edges between nodes on the same layer are not allowed and edges spanning multiple layers are split into chains of dummy nodes. Layer assignment is usually computed with the goal of minimizing edge-length (and hence the number of dummy nodes). The layer assignment methods used are generally incapable of handling cyclic-digraphs and so preprocessing is required to make the graph acyclic by reversing a minimal number of edges. Assigning the x-coordinates is normally done in two stages: first ordering nodes within layers to minimize crossings and then exact placement subject to the computed ordering to optimize aesthetic criteria such as minimizing edge bends. Each of the optimization problems outlined above has been shown to be NP-hard so heuristic approaches have been designed that offer reasonable results in most cases.
Carmel et al. see e.g., L. Carmel, D. Harel and Y. Koren, “Combining Hierarchy and Energy for Drawing Directed Graphs”, IEEE Trans. Visualization and Computer Graphics 10 (2004), 46-57, is an other known approach to drawing digraphs. In this approach, the nodes are associated with continuous y-coordinates, in a way that can be applied to any kind of digraph, whether cyclic or acyclic, and which requires no graph modification or preprocessing. These y-coordinates are the unique minimizer of the hierarchy energy, which strongly reflects the directional information of the digraph. The x-coordinates are the minimizer of another energy function that disregards all directional information. The main characteristics of this method are its ability to deal with cyclic graphs, the fact that nodes are not partitioned into horizontal layers and the very fast execution. However, although solutions are defined for graphs with cycles, so-called symmetric nodes within cycles are by definition considered to be at the same hierarchy level and are thus assigned the same y-coordinate. The resulting drawings make such cycles difficult to see, see, e.g., FIG. 5B.
Currently, a need exists for an improved method and system for constructing graphs including digraphs.